--输入n个整数，输出其中最小的k个。
--输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。
require("dump");
local CTree =  {} ; --用线性表来构建 节点 i 的左节点 为2*i ,右节点为2*i+1 ;

--[[
 -- 上升操作
 -- @DateTime 2018-08-03
 -- @return   [description]
 ]]
-- CTree._shiftUp = function(data,index)
-- 	while(math.floor(index/2)>0 and CTree[math.floor(index/2)]<CTree[index]) do
-- 		CTree._swap(math.floor(index/2),index);
-- 		index = math.floor(index/2) ;
-- 	end
-- end

CTree._swap = function(a,b)
	local temp = CTree[a] ;
	CTree[a] = CTree[b] ;
	CTree[b] = temp ;
end

-- 大顶堆
CTree._shiftUp = function(index)
	local parentIndex = math.floor(index/2) ;
	if(parentIndex>0) then
		if(CTree[math.floor(index/2)]<CTree[index]) then
			CTree._swap(math.floor(index/2),index);
			CTree._shiftUp(math.floor(index/2)) ;
		end
	end
	return ;
end


-- 小顶堆
-- CTree._shiftUp = function(index)
-- 	local parentIndex = math.floor(index/2) ;
-- 	if(parentIndex>0) then
-- 		if(CTree[math.floor(index/2)]>CTree[index]) then
-- 			CTree._swap(math.floor(index/2),index);
-- 			CTree._shiftUp(math.floor(index/2)) ;
-- 		end
-- 	end
-- 	return ;
-- end

--大顶堆调整
CTree._shiftDown = function(index)
	if(CTree[2*index] and CTree[2*index + 1]) then
		if(CTree[2*index]>CTree[2*index + 1]) then
			if(CTree[2*index]>CTree[index]) then
				CTree._swap(index,2*index); --和左节点交换
				CTree._shiftDown(2*index); --递归继续调整树
			end	
		else
			if(CTree[2*index+1]>CTree[index]) then
				CTree._swap(index,2*index+1); --和左节点交换
				CTree._shiftDown(2*index+1); --递归继续调整树
			end
		end
	elseif CTree[2*index] and CTree[2*index] >CTree[index] then --存在一个子节点只会是左节点
		CTree._swap(index,2*index); --和左节点交换
		CTree._shiftDown(2*index); --递归继续调整树
	end
	return ;
end


--小顶堆调整
-- CTree._shiftDown = function(index)
-- 	if(CTree[2*index] and CTree[2*index + 1]) then
-- 		if(CTree[2*index]<CTree[2*index + 1]) then
-- 			if(CTree[2*index]<CTree[index]) then
-- 				CTree._swap(index,2*index); --和左节点交换
-- 				CTree._shiftDown(2*index); --递归继续调整树
-- 			end	
-- 		else
-- 			if(CTree[2*index+1]<CTree[index]) then
-- 				CTree._swap(index,2*index+1); --和左节点交换
-- 				CTree._shiftDown(2*index+1); --递归继续调整树
-- 			end
-- 		end
-- 	elseif CTree[2*index] and CTree[2*index] <CTree[index] then --存在一个子节点只会是左节点
-- 		CTree._swap(index,2*index); --和左节点交换
-- 		CTree._shiftDown(2*index); --递归继续调整树
-- 	end
-- 	return ;
-- end

--[[
 -- 插入节点
 -- @DateTime 2018-08-03
 -- @return   [description]
 ]]
CTree.insert = function(data)
    table.insert(CTree,data) ;
    CTree._shiftUp(data,#CTree);
end


--[[
  移除最顶端节点 
 ]]
CTree.remove = function()
    if(#CTree==1) then
    	return table.remove(CTree);
    end
    if(#CTree==0) then
    	return ;
    end
	local node = CTree[1];
	CTree[1] = table.remove(CTree);
	--dump(CTree,"remove")
	CTree._shiftDown(1);
	return node
end



---构建一颗完全二叉树
function createCompleteBiTree()
	 local data = {1,2,3,4,5,6,7,8,9} ;
	 for i=1,#data do
	 	if (data[i]) then
	 		CTree.insert(data[i])
	 	end
	 end
	-- dump(CTree);
	 while(#CTree>0) do
	 	print(CTree.remove())
	 	--dump(CTree) ;
	 end
end

-- createCompleteBiTree();

local n= 8;
local k=4;
local data = {1,2,3,4,5,6,7,8};
for i=1,#data do
	if(#CTree==k) then
		if(data[i]<CTree[1]) then
			CTree.remove();
			CTree.insert(data[i]);
		end
	else
		CTree.insert(data[i]);
	end
end

dump(CTree,"root--->");
--构建一个元素个数为k的小顶堆

